1. Field of the Invention
The present invention relates to an image processing apparatus and an image processing method. In particular, the present invention relates to an image processing apparatus and an image processing method for quantizing multi-gradation image data to convert it into pseudo halftone output image data.
2. Description of Related Art
Conventionally, an ordered dither method, an error diffusion method or the like have been known as a quantization processing method for converting multi-gradation original image data into pseudo halftone output image data. Among the above methods, the error diffusion method has been often used for high quality images and improved variously, because it can provide relative high quality images. An object as for the image quality in the error diffusion method is of how to reduce the texture specific to an algorism without amplifying noises.
For example, it is disclosed that securing uniformity is attempted by using a plurality of error diffusion matrices (refer to JP-Tokukaihei-4-328957A discloses). Specifically, switching two matrices according to input values, using a large matrix to a highlight part or a shadow part, preventing generation of pattern called “worm”, and minimizing noises are disclosed.
Further, it is also disclosed that changing a threshold value by using a threshold value depended on an output value, in order to obtain further uniformity in a highlight part or a shadow part (refer to JP-Tokukaihei-8-107500A). Specifically, what is disclosed are performing threshold value change corresponding to input, with respect to a neighboring pixel, depending on whether bilevel halftoning output is white or black, and using the threshold value change repeatedly.
In addition to the above, methods for optimizing the size and the coefficient of an error diffusion matrix, changing of processing order (that is, scan direction) or the like have been performed. Although it was possible to obtain certain effects by using the above means, the effects were not sufficient.
On the other hand, an anti-correlation digital halftoning method is supposed as the quantization processing means different from the error diffusion method or improved method thereof and the dither method (refer to “Anti-Correlation Digital Halftoning”, Dmitri A. Gusev, August 1998, Indiana University, Published online Jul. 1, 2003, Internet Published at indiana.edu. This method is for setting an array (hereinafter, referred to as a dot appearance pattern) representing dot appearance information for every pixel, that is, dot presence/absence information of the number substantively proportional to the number of gradations composed of an observed pixel, and for performing halftoning on the basis of the information. In order to decide the content of dot appearance pattern of the observed pixel, the method includes: using the dot appearance pattern which has been already decided to neighboring pixels of the observed pixel; calculating expectation value (hereinafter, referred to as a histogram) of the dot appearance in the neighboring pixels for every element number of elements composing the dot appearance pattern; setting dot presence information preferentially to the element number of which the dot appearance number is small, on the basis of the expectation value; and deciding the dot appearance pattern of the observed pixel so as to set dot absence information to the element number of which dot appearance number is large.
Hereinafter, the anti-correlation digital halftoning method will be explained with concrete examples. In the following explanation, the processing is performed with changing the observed pixel from left to right.
As shown in FIG. 30, in the image processing by the anti-correlation digital halftoning method, a random valuable r (r is an integral value) is previously determined at random from the range of 0 to (n−1) (Step T1), before original image data (multi-gradation image data) are input. “n” is the maximum number of a pixel value gi,j. The pixel value gi,j is a gradation value of the pixel in i-th row and the j-th column, and is any one of values in the range of 0 to n.
After the original image data are input, the pixel value gi,j of the pixel (the observed pixel) in i and row j column is obtained from the original image data (Step T2).
After the pixel value gi,j is obtained, a local filter P of the pixel in the i-th row and the j-th column is generated on the basis of the pixel value gi,j (Step T3). Concretely, first, Δ is obtained by assigning the pixel value gi,j to the following formula (1). Then, the range of the left column of FIG. 31 where the obtained belongs is specified. Thereby, the information of the local filter P corresponding to the specified range is specified from the right column of FIG. 31. Incidentally, in FIG. 31, for example, “Δε[0, 13/255)” means “0≦Δ<13/255”.Δ=|gi,j−n/2|/n  (1)
For example, if the pixel value gi,j is 120, “Δ=|120−255/2|/255=7.5/255” is derived by the above formula (1). Then, it can be specified that the Δ (7.5/255) belongs to “Δε[0, 13/255)” described in the most upper cell of the left column of the table in FIG. 31. Thereby, R(K1, 6, −5), which is described in the cell to the right of the above specified cell where “Δε[0, 13/255)” is described, can be specified as the information of the local filter P.
Next, when the specified information is conveniently generalized to define as “R(K, lk, ε(lk)”, first, any one of six basic filters K1 to K6 shown in FIGS. 32A to 33C is selected with reference to the “K”. Next, a filter with lk rows×(2lk−1) columns having breadth for (lk−1) pixels from the pixel marked with “x”, that is, the pixel in the i-th row and the j-th column, in the upper, left and right direction respectively, is generated. Then, with reference to the “lk” and “ε(lk)”, the pixel number of the basic filter K is applied directly to each of pixels from the 1st column to the (lk−ε(lk))-th column of the generated filter. Moreover, 0 is applied to each of pixels beyond the (lk−ε(lk))-th column. Thereby, the local filter P is generated.
For example, if the information of the local filter P is represented as R(K6, 4, −1), the local filter P is generated with the following procedures. That is, in the R(K6, 4, −1), the entry corresponding to the basic filter K is “K6”, and therefore, a basic filter K6 shown in FIG. 33C is specified as the basic filter K from three basic filters K4 to K6 respectively shown in FIGS. 33A to 33C. Then, in the R(K6, 4, −1), the entry corresponding to lk is “4”, and the entry corresponding to ε(lk) is “−1”. Therefore, first, a filter with 4 rows×7 (=2×4−1) columns having breadth for 3 (=lk−1) pixels in the upper, left and right direction respectively from the pixel marked with “x” in the basic filter K6 in FIG. 33C, is generated. After that, in the generated filter with 4 rows×7 columns, the pixel number of the basic filter K6 is applied directly to each of pixels from the 1st column to the 5th (=4−(−1)) column. Moreover, 0 is applied to each of pixels beyond the 5th column. The local filter P generated with the above procedures is shown in FIG. 34.
After the local filter P is generated, a histogram Hi,j[k] of the pixel in the i-th row and the j-th column is calculated (Step T4). The “histogram Hi,j[k]” means the sum value (the expectation value) which is obtained as follows; that is, when each arrangement position of the neighboring pixel of the observed pixel indicated by “x” in the local filter P is represented by (x, y), each dot appearance pattern Cx,y[k] of the neighboring pixel of the observed pixel is weighted with the pixel value of the pixel in the position of (x, y) of the local filter P and added one another for every value of an element (an element number) k. In this regard, however, “k” is an arbitrary integral value from 0 to (n−1), and is synonymous with the element (the element number) k of the dot appearance pattern Cx,y[k]. Further, “the dot appearance pattern Cx,y[k]” is the sequence (the dot appearance information array) composed of Ci,j[0] to Ci,j[n−1] respectively taking the value of 0 and 1. In this case, when any one of values from 0 to (n−1) is assigned to the element k, if the dot appearance pattern Ci,j[k] is “1”, it denotes that a dot is formed in the pixel in the i-th row and the j-th column, and if the dot appearance pattern Ci,j[k] is “0”, it denotes that a dot is not formed.
For example, when the local filter P shown in FIG. 34 is generated, if the position (x, y) of each pixel and the pixel value px,y of each pixel in the local filter P are set as shown in FIGS. 35A and 35B respectively, the histogram Hi,j[k] of the observed pixel (the pixel marked with “x” in FIGS. 34, 35A and 35B) in the i-th row and the j-th column is calculated for every value of an element (an element number) k, according to the following Formulas.Hi,j[0]=Cx1,y1[0]×px1,y1+Cx1,y2[0]×px1,y2+Cx1,y3[0]×px1,y3+ . . . +Cx4,y3[0]×px4,y3 Hi,j[1]=Cx1,y1[1]×px1,y1+Cx1,y2[1]×px1,y2+Cx1,y3[1]×px1,y3+ . . . +Cx4,y3[1]×px4,y3 Hi,j[2]=Cx1,y1[2]×px1,y1+Cx1,y2[2]×px1,y2+Cx1,y3[2]×px1,y3+ . . . +Cx4,y3[2]×px4,y3 . . .. . .Hi,j[n−1]=Cx1,y1[n−1]×px1,y1+Cx1,y2[n−1]×px1,y2+Cx1,y3[n−1]×px1,y3+ . . . +Cx4,y3[n−1]×px4,y3 
Next, the histograms Hi,j[0] to Hi,j[n−1] respectively calculated for each element k are rearranged in ascending order. Then, an element number array S[k] for the histogram Hi,j[k] is calculated (Step T5).
For example, when the histograms Hi,j[0] to Hi,j[n−1] are rearranged in the order of “Hi,j[8]<Hi,j[3]<Hi,j[4]<Hi,j[1]<Hi,j[5]< . . . <Hi,j[n−1]”, the element number array S[k] is calculated as {8, 3, 4, 1, 5, . . . , (n−1)}. Incidentally, in the element number array S[k], “8” is the 0th element and “3” is the 1st element.
After the element number array S[k] is calculated, a count value Count is set to 0 (Step T6). Then, the value of the element S[Count] in the order corresponding to the value of the count value Count among the element number array S[k] is assigned to the element k′ of the element number array S[k] (Step T7). That is, for example, in the above case of the element number array S[k] (={8, 3, 4, 1, 5, . . . , (n−1)}), because the count value Count is “0”, “8” (=S[0]) is assigned to the k′.
Accordingly, the relation between the count value Count and the pixel value (gi,j−1) is compared (Step T8).
As the result of the comparison, if the count value is equal to or less than the pixel value (gi,j−1), the dot appearance pattern Ci,j[k′] corresponding to the element k′ is set to “1” (Step T9), or if the count value is more than the pixel value (gi,j−1), the dot appearance pattern Ci,j[k′] corresponding to the element k′ is set to “0” (Step T10). For example, when the pixel value (gi,j−1) is “3” and the element number array S[k] is {8, 3, 4, 1, 5, . . . , (n−1)}, first, the element Ci,j[8] is set to “1”, among the dot appearance pattern Ci,j[k].
After the processing in Step T9 or Step T10 is completed, “1” is added to the count value Count (Step T11), the relation between the count value Count (=1) and (n−1) is compared (Step T12), the processing from Step T7 to Step T11 are repeated until the count value Count becomes the same value as (n−1), and thereby, the dot appearance pattern Ci,j[k′] is decided. Thereby, the elements Ci,j[8], Ci,j[3] and Ci,j[4] are set to “1” as described above. After the dot appearance pattern Ci,j[k] is decided, Ci,j[r] of which element number is random variable r determined in above Step T1 is calculated as an output value bi,j of the pixel in the i-th row and the j-th column, among the dot appearance pattern Ci,j[k] (Step T13). Incidentally, the output value bi,j is “0” or “1” as can be seen from the processing of above Step T9 or Step T10.
After the output value bi,j is calculated, it is judged whether or not the output values b have been calculated with respect to all the pixels of the input original image data (Step T14). If it is judged that the output values b of all the pixels is not calculated, the processing from above Step T2 to Step T13 are repeated with respect to each unprocessed pixel. If it is judged that the output values b of all the pixels, that is, the output image data of pseudo halftone is calculated, the processing is ended.
According to the image processing by the above anti-correlation digital halftoning, when one pixel is focused, dot appearance frequency is proportional to the pixel value of the pixel. Further, when a plurality of pixels adjacent each other are focused, the dot in each of pixels appears so as to maximize the anti-correlation with the neighboring pixels substantially. Therefore, the dispersibility of the dots formed on a recording medium while an image recording is improved. Therefore, the anti-correlation digital halftoning method has the feature that there are few textures peculiar to the error diffusion method.
Incidentally, for deciding the dot appearance pattern Ci,j[k] with respect to the end portion of an image, the dot appearance pattern with respect to the neighboring pixels other than an area of the image is required. Therefore, for the neighboring pixels other than an area of the image, the dot appearance pattern is previously decided by using a random valuable or the like. In particular, for example, the dot appearance pattern is defined as follows.Ci,j[k]=1(rBR<nΔ),0(rBR≧nΔ)
Hereupon, Δ=|gi,j−n/2|/n, and “gi,j” is the pixel value of the observed pixel. Further, “rBR” is a random valuable included in {0, 1, . . . (int)(n/2)} and is different value every time.
However, in the above anti-correlation digital halftoning method, there are following problems.
In the first place, in the case where the anti-correlation digital halftoning method is applied to a color image or a grayscale image resolved for every different density, because the dot arrangement between the different colors is not concerned, the color heterogeneity is easily generated. Further, the local variation of lightness becomes random, and accordingly, the roughness is increased.
In the second place, the anti-correlation digital halftoning method comprises the outstanding feature that the dispersibility for the bilevel halftoning of a monochrome image is well. However, the anti-correlation digital halftoning method sometimes generates the pattern comprising a regular periodic structure with respect to a specific input value. As the problems being spoken generally, although it seems that the simple periodic pattern is preferred as the result of the halftoning of the input data with a certain level, on the other hand, the border where the data value changes is enhanced and a pseudo outline is generated in many cases.
In the anti-correlation digital halftoning method, because a certain level of consideration has been already given, it is difficult to generate the periodic pattern as that generated by the common Floyd-Steinberg type error diffusion method. However, the periodic structure is sometimes generated with respect to a specific image pattern. For example, it has been known that although the pseudo outline is not outstanding with respect to the gradation pattern (ramp input), a regular checker pattern is sometimes generated in the portion where the 50% value constantly continues in a wide range.
In the third place, there is the case where the generation of continuous dots is required in the highlight part of the image, by the printing method of printers such as electro-photographic system or the like.
However, conventionally, the generation probability of a systematic dot arrangement or a different dot arrangement has not been controlled. Therefore, the dot arrangement of the processed image strongly depends on the image. Further, the effect of the processing is unstable because of indetermination of the shape of the dot arrangement or interference of a different dot arrangement.
In the fourth place, in the case where the anti-correlation digital halftoning method is applied to a color image or a grayscale image resolved for every different density, if the dispersibility between the non-recording dot and the low occupancy rate dot in the case where the summation of the occupancy rate per different dot unit area is not more than 100%, or the dispersibility between the overlapped recording dots and the low occupancy rate dot in the case where the summation of the occupancy rate per different dot unit area is more than 100% is worse, the periodic structure becomes to be outstanding. However, because those relations have not been considered conventionally, the dot dispersibility sometimes becomes worse when there is the dot of which occupancy rate is low.